The demand for networked digital audiovisual systems is expected to grow over the next few years, as business, government and other institutions increasingly turn to digital networks to distribute audiovisual information for education, presentations and reference applications. These customers expect systems that will allow a number of people to be able to view audiovisual information from a server simultaneously, while fully retaining their other network functions. For example, in business computing, most of the major productivity software developers see networked video as an effective means of training and supporting users. Many of these developers have begun including VHS videotapes for training with their software. Now they want to take this a step further by linking the video directly to their software's on-line help resources. Centralizing that support in a video server reduces the cost for customers with many users and ensures that it is properly maintained by the responsible persons.
Networked video presentation systems in business can allow corporate resources, such as sales videos, employee information, and video-based training to be available immediately to all employees from their desks. Similarly, networked video documentation systems will allow institutions of all kinds to maintain multi-user audiovisual databases. The largest population of users of such systems are likely to be health care institutions which have extensive audiovisual records. In addition, such databases can be used for on-the-job reference such as revisiting a complex procedure on the manufacturing floor, or creating on-line archive of TV commercials for an advertising agency.
Audiovisual communication including video conferencing, video mail, collaborative work, is yet another fast growing business application which requires the support of networked video over local area networks.
The characteristics of video traffic differ substantially from those of traditional data traffic to the point that local area networks designed primarily to support data applications are not appropriate to effectively support video services. With data applications, the data rate associated with a traffic source is highly variable; i.e., it exhibits a high peak to average ratio. Accordingly, the design of local area networks aimed at supporting data applications has been based on the principle of bandwidth sharing and statistical time multiplexing. In contrast, the data rate associated with the transmission of a video stream is relatively constant; the precise value depends on the particular encoding scheme used and the images quality desired, but it tends to be much higher than the average rate associate with a data traffic source. In particular, CCITT recommendation H.261 specifies video coding and decoding methods for audiovisual services at the rates of p .times.64 Kbits/s, where p is in the range 1 to 30; the MPEG standard specifies a coded representation that can be used for compressing video sequences to bit rates around 1.5 Mbits/s; Intel's DVI video streams have a data rate of 1.2 Mbits/s; the successor to MPEG, known as MPEGII, is being developed to provide a wider range of functionality and image quality than its predecessor at rates in the range of 4 to 8 Mbits/s.
Two important observations can be made. The first is that the volume of bits corresponding to a video segment of useful duration is large. A ten minute DVI video segment corresponds to 90 Mbytes. Ten hours correspond to over 5 Gbytes. Thus video servers for use in systems where shared video information is to be stored must be of relatively high capacity.
The second observation is that the transmission of a video signal of a certain data rate over a local area network requires the provision of a channel of the same data rate on a continuous basis so as to achieve timely delivery of the data. To support the transmission of multiple independent such video signals in a local area environment would require a network which can guarantee the bandwidth required for each video signal, and which has an aggregate bandwidth exceeding that required for the maximum configuration expected.
For a small number of users, simple and inexpensive solutions, such as Ethernet and token ring, may be adequate. For example, 5 DVI channels have an aggregate bandwidth of 6 Mb/s, well within the range of both Ethernet and the token ring network. But as the number of users increases, the required aggregate bandwidth of the network exceeds that of a single Ethernet or ring network, and other solutions are needed. One solution may be found in FDDI. This solution requires that each client be equipped with an FDDI interface card, which is substantially more expensive than the Ethernet card, while the client needs only a fraction of its capabilities. As simple and inexpensive interface cards at the client (e.g., Ethernet cards), are quite attractive and fairly widespread, it is desirable to look for a solution that could integrate such interfaces while meeting the bandwidth requirements for the maximum configuration. A possible solution is to use several Ethernet segments or ring networks, each supporting a small number of clients, and interconnect these segments via bridges. Each segment would then have to carry the traffic corresponding to the clients connected to it. The problem with this approach is that managing and controlling the video streams over an internet involving bridges and gateways proves to be quite complex. If a video server which handles all video streams is present, it requires a high bandwidth connection to the internet, and thus may have to be connected to all segments. A more attractive and flexible approach is the use of a star configuration with a switching hub in the center which guarantees a clear Ethernet channel or clear ring channel to each client over a dedicated twisted pair. In this configuration, the control of video streams and data traffic and the effect of one on another can be accomplished effectively in the hub. The server is also naturally connected to the hub via a link of sufficiently high data rate to support all video streams. The link may consist of multiple parallel Ethernet connections, or may be a joint-to-point FDDI link.
FIG. 1 schematically illustrates a system 10 comprising a plurality of stations 13 which communicate via a shared broadcast-type transmission medium 15 having a total bandwidth of W bits/s. Each station 13 is connected to the network 15 by means of a half-duplex link 17 of rate V bits/s and a port 19. As shown in FIG. 2, each port 19 comprises a transmit FIFO buffer 21 and a receive FIFO buffer 23, of capacity Bt and Br bits, respectively. In some cases, there may be more than one receive buffer at a port.
The transfer of data between a particular pair of stations 13 takes place in the form of packets of variable size, the maximum of which is denoted by P.sub.max, and follows three steps: the packet is first transmitted by the sending station to its port, and is queued in the transmit buffer at that port; when it reaches the head of the queue, it is transmitted over the transmission medium 15 to the port to which the receiving station is connected, and is stored in its receive buffer; finally it is transmitted from the latter to the receiving station.
There are two types of shared resources in the system 1 of FIG. 1: one is the transmission medium 15 which all ports share to transmit packets; the other is the (finite) receive buffers at the ports for which incoming packets from various ports contend. Mechanisms are required to allocate these resources to requesters in an efficient and fair manner.
In the system 10 of FIG. 1, access to the transmission medium 15 is controlled by a token-passing round-robin mechanism. Such an access mechanism is simple to implement, and provides an efficient and fair allocation of the medium's bandwidth among transmitting stations at all times.
When, in the system 10 of FIG. 1, V is greater than or equal to W, and all stations 13 give priority to packet receptions over packet transmissions, then the receive buffers 23 are never full, and the transmission medium 15 is the only shared resource in the system. In this case, the token-passing mechanism is all that is needed. In most cases, however, V is smaller than W. As a result, depending on the traffic pattern among stations, it is likely at times for the particular receive buffer 23 at a particular port 19 to become full, and for packets being transmitted on the medium 15 and addressed to that particular port to be rejected. As the particular receive buffer (which gets emptied at the rate of V bits/s) becomes capable of accepting packets addressed to it, the question arises as to which sending port should be given the right to access the buffer. If the access right were given to the first sending port with a packet destined to that particular receive buffer which happens to capture the token, (i.e., if one were to allow the token passing mechanism to regulate access to receive buffers), then a certain degree of unfairness may result, in that it would be possible for some sending ports to monopolize the use of such receive buffers, while other sending ports are blocked repeatedly. Thus, an additional mechanism needs to be introduced to guarantee fair access to the receive buffers. It is an object of the present invention to provide a process for achieving fair access to such receive buffers.
Certain applications require that packets be prioritized, and that a certain degree of preference be given to higher priority packets when present. For example, as indicated above, in a network which handles video and non-video data, it is often necessary to give video information priority over non-video information in order to maintain the quality of real time video transmissions. Consider that there are K priority levels (0 representing the highest level, and K-1 the lowest), and that a single priority value is assigned to each packet. It is a further object of the invention to provide access to the receive buffers according to a process which gives higher priority packets preferential access to receive buffers when congestion occurs.
Clearly, should congestion at a receive buffer occur and persist over time, giving absolute priority access to higher priority packets could cause a lower priority packet waiting at the head of the queue at some port to be blocked repeatedly for a long time. This situation is undesirable, especially since there may be packets waiting behind the blocked one, possibly of higher priority and/or destined to other (possibly uncongested) ports which are also blocked (an effect referred to as head-of-the-line (HOL) blocking). It is a further object of the process of the present invention to provide a solution to the head-of-the-line blocking problem, while guaranteeing fairness within each priority class.